home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 5686 < prev    next >
Encoding:
Text File  |  1996-08-05  |  17.6 KB  |  678 lines
  1. Path: news.microsoft.com!news
  2. From: a-cnadc@microsoft.com (Dann Corbit)
  3. Newsgroups: comp.lang.c
  4. Subject: Tough Question: The summary. WARNING LONG! - tough.cpp [1/1]
  5. Date: 20 Feb 1996 22:25:13 GMT
  6. Organization: Microsoft Corporation
  7. Message-ID: <4gdho9$mll@news.microsoft.com>
  8. NNTP-Posting-Host: 157.57.171.202
  9. Mime-Version: 1.0
  10. Content-Type: multipart/mixed;
  11.      Boundary="*-*-*- Next Section -*-*-*"
  12. X-Newsreader: WinVN 0.93.14
  13.  
  14. --*-*-*- Next Section -*-*-*
  15.  
  16. I put most of the code samples that were submitted into a C
  17. driver and tested them.  I may well have goofed some of them
  18. up, so code failures may be due to me.
  19.  
  20. About half of them worked (up to 1000 as specified ) and half
  21. didn't.
  22.  
  23. Of the versions that worked, there were huge differences in 
  24. speed.
  25.  
  26. Also included is a new version that is faster than any of 
  27. the original suggestions.  At the same time it is rather
  28. unsatisfying since it just looks up the answer in Dik Winter's
  29. table.
  30.  
  31. Anyway, here are the routines, along with the test driver.
  32. The results for one of my machines are also included.
  33.  
  34. -- 
  35. The opinions expressed in this message are my own personal views 
  36. and do not reflect the official views of Microsoft Corporation.
  37. --*-*-*- Next Section -*-*-*
  38.  
  39. /*************************************************************************
  40. PROBLEM DEFINITION:
  41.  
  42. From: thecrow@iconn.net ( The Crow )
  43. Subject: Tough FACTORIAL math problem...
  44. Date: 13 Feb 1996 23:54:22 GMT
  45.  
  46. Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  47. given factorial.  For instance,
  48.  
  49. 5! = 120
  50.  
  51. so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  52. Problem is, no matter how huge of a data-type you use, there isn't any way for
  53. the computer to handle 1000!, it is however possible to find the last non-zero
  54. digit somehow.  One thing I have tried is as I went through mulitplying the
  55. series of numbers in the factorial ( 5 * 4 * 3 * 2 ) I would remove all the
  56. trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i
  57. am not really sure why.  If anyone has a clue how I can do this let me know.
  58. ***************************************************************************/
  59. #ifdef TEST
  60. /* Dik Winter's table:
  61. If you wish to try, below follows a table with the last non-zero digits of
  62. all factorials up to ( and including ) 1000!.  Check your output with this
  63. table.
  64. { ammended by d.  corbit to include 0!}
  65. */
  66. static char gpszFactorialLastDigits[] = {
  67.    "112642242888682886824484644846886822242822428662642"
  68.    "24284484666264662648868244846886822242822428662644"
  69.    "48468868222428224286626488682662644484644846224282"
  70.    "24284484666264662648868266264224288868288682448462"
  71.    "24284484666264662648868222428448466626466264886828"
  72.    "86826626444846448462242822428448466626466264886826"
  73.    "62642242888682886824484622428448466626466264886822"
  74.    "24284484666264662648868222428448466626466264886828"
  75.    "86826626444846448462242844846886822242822428662648"
  76.    "86826626444846448462242888682662644484644846224284"
  77.    "48468868222428224286626466264224288868288682448468"
  78.    "86826626444846448462242866264224288868288682448466"
  79.    "62642242888682886824484666264224288868288682448464"
  80.    "48468868222428224286626422428448466626466264886824"
  81.    "48468868222428224286626444846886822242822428662648"
  82.    "86826626444846448462242822428448466626466264886826"
  83.    "62642242888682886824484622428448466626466264886822"
  84.    "24284484666264662648868288682662644484644846224282"
  85.    "24284484666264662648868266264224288868288682448462"
  86.    "24284484666264662648868222428448466626466264886822"
  87. };
  88. int iLastDigit( int i )
  89. {
  90.    int j;
  91.    j = ( int ) gpszFactorialLastDigits[i] - '0';
  92.    return j;
  93. }
  94. #endif
  95.  
  96. extern int __cdecl foo( int n );
  97. extern int __cdecl foo2( int n,int *x,int *y );
  98. extern int __cdecl lastdigit( unsigned long iVal );
  99. extern int __cdecl last_digit( int num );
  100. extern int __cdecl last_digit2( int num );
  101. extern int __cdecl last_digit2a( int num );
  102. extern int __cdecl last_non_zero_digit_of_factorial( int n );
  103. extern int __cdecl main( int argc,char **argv );
  104. extern int __cdecl odds( int n,int *x,int *f );
  105. extern int __cdecl rightmost_nonzero_digit( int n );
  106. extern int __cdecl rtDigit( int n );
  107. extern long __cdecl factorial_lsd( long n );
  108. extern unsigned long __cdecl eliminate_fives( unsigned long *i );
  109. extern unsigned long __cdecl eliminate_twos( unsigned long *i );
  110. extern unsigned long __cdecl right_digit( unsigned long i );
  111. extern void __cdecl getLastFactorialDigits( int *results,int n );
  112. extern int __cdecl ShowLastFactorialDigit( int results[], int n );
  113. static int __cdecl f( int i );
  114. static int __cdecl lastNonZeroDigitOfFactorial( int i );
  115.  
  116. /* Dik Winter */
  117. int fact_lsd(long n)
  118. {
  119.    long r = 1, i, i1;
  120.    if(n > 1)
  121.    {
  122.       for(i = 1, i1 = 1; i <= n; i++, i1 = i)
  123.       {
  124.          /* cast out factors 5 */
  125.          while(i1 % 5 == 0)
  126.          {
  127.             i1 /= 5;
  128.             /* multiply by 5 divide by 10, equivalent to divide by 2. */
  129.             r >>= 1;
  130.             /* except for 1! and 0! the last non-zero digit is even. */
  131.             if(r & 1) r += 5;
  132.          }
  133.          r = (r * i1) % 10;
  134.       }
  135.    }
  136.    return r;
  137. }
  138. /* Dann Corbit */
  139. long factorial_lsd( long n )
  140. {
  141.    long result=1, i;
  142.  
  143.    if ( n > 1 )
  144.       for ( i=1; i<=n; i++ )
  145.       {
  146.          result *= i;
  147.          while( result%10 == 0 )
  148.          {
  149.             result /= 10;
  150.          }
  151.          result %= 100000L;
  152.       }
  153.    return result%10;
  154. }
  155.  
  156. //From:ian@rsd.bel..alcatel.be ( Ian Ward )
  157. int last_digit ( int num )
  158. {
  159.    static int tens [4] = {
  160.       8, 4, 2, 6
  161.    };
  162.    static int singles [10] = {
  163.       1, 1, 2, 6, 4, 2, 2, 4, 2, 8
  164.    };
  165.    int single = singles [num % 10];
  166.    if ( num > 9 ) single *= tens [( num/10-1 ) % 4];
  167.    return single % 10;
  168. }
  169.  
  170. //From: ian@rsd.bel.alcatel.be ( Ian Ward )
  171. int last_digit2 ( int num )
  172. {
  173.    static int fred [] =
  174.    {
  175.       1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 8, 8,
  176.       6, 8, 2, 6, 6, 2, 6, 4, 4, 4, 8, 4,
  177.       6, 8, 8, 6, 8, 2, 2, 2, 4, 2, 8, 4,
  178.       4, 8, 4, 6, 6, 6, 2, 6, 4, 2, 2, 4, 2, 8
  179.    };
  180.    return fred[ num>9 ? 10+( ( num-10 )%40 ) : num ];
  181. }
  182.  
  183. //From: kcline@sun132.spd.dsccc.com ( Kevin Cline )
  184.  static int table[9][9] =
  185. {
  186.    {1, 2, 0, 4, 0, 6, 0, 8, 0 },
  187.    {2, 4, 0, 8, 0, 2, 0, 6, 0 },
  188.    {0, 6, 0, 2, 0, 8, 0, 6, 0 },
  189.    {0, 8, 0, 6, 0, 4, 0, 2, 0 },
  190.    {0, 4, 0, 8, 0, 2, 0, 6, 0 },
  191.    {0, 2, 0, 4, 0, 6, 0, 8, 0 },
  192.    {0, 4, 0, 8, 0, 2, 0, 6, 0 },
  193.    {0, 6, 0, 2, 0, 8, 0, 6, 0 },
  194.    {0, 8, 0, 6, 0, 4, 0, 2, 0 }
  195. };
  196.  
  197.  
  198.  
  199.  
  200. int last_non_zero_digit_of_factorial( int n ) {
  201.    int digit = 1, i;
  202.    for ( i = 2; i < n ; ++i ) {
  203.       while ( i % 10 == 0 ) i /= 10;
  204.       digit = table[digit-1][i-1];
  205.    }
  206.    return digit;
  207. }
  208.  
  209. //From: jscuste@sandia.gov ( Jon Custer )
  210. /* Determine last non-zero digit in a factorial */
  211. /*
  212.  General algorithm:
  213.  1 ) Eliminate all powers of 2 as they come along.  Keep track of _net_
  214.  number of powers of 2 ( see next step ).  Last digit of this
  215.  factor is easy to determine in a look up table.
  216.  2 ) Eliminate all powers of 5 as they come along.  Take away powers of
  217.  2, leaving _net_ powers of 2, to convert to powers of 10.
  218.  There are always more powers of 2 than powers of 5.
  219.  All powers of 10 result in no change to last significant digit.
  220.  3 ) Multiply remainder of factor with previous residual.  Truncate
  221.  to last digit, and reserve for next iteration.  Multiply by
  222.  last digit of _net_ powers of two, take last digit as answer.
  223.  4 ) Print out result, and loop to next.
  224. */
  225.  
  226. #include <stdlib.h>
  227. #include <stdio.h>
  228.  
  229. /* function prototypes */
  230. unsigned long right_digit( unsigned long i );
  231. unsigned long eliminate_fives( unsigned long *i );
  232. unsigned long eliminate_twos( unsigned long *i );
  233.  
  234. int lastdigit( unsigned long iVal ){
  235.  
  236.    /* keep track of powers of 5s, powers of 2s so far */
  237.    unsigned long p_of_5 = 0ul;
  238.    unsigned long p_of_2 = 0ul;
  239.  
  240.    static unsigned long lookup[4] = {
  241.       6ul, 2ul, 4ul, 8ul
  242.    };
  243.  
  244.    unsigned long one;
  245.    unsigned long k;
  246.  
  247.  
  248.  
  249.    /* special cases here - 0! and 1! */
  250.    if ( iVal == 0 || iVal == 1 )
  251.       return 1;
  252.  
  253.    /* Initialize last digit */
  254.    one = 1ul;
  255.  
  256.    /* drop all 2's from next factor, keep track of number */
  257.    p_of_2 += eliminate_twos( &iVal );
  258.  
  259.    /* drop all 5's from factor */
  260.    k = eliminate_fives( &iVal );
  261.    p_of_5 += k; /* keep track of total 5's */
  262.    p_of_2 -= k; /* eliminate 2's to make 10s */
  263.  
  264.    /* multiply remainder and take last digit ( always non-zero ) */
  265.    one = right_digit( one*iVal );
  266.  
  267.    /* now correct for all the powers of two so far */
  268.    return right_digit( one*lookup[( p_of_2 % 4 )] );
  269.  
  270. }
  271.  
  272. unsigned long right_digit( unsigned long i ){
  273.    return ( i % 10ul );
  274. }
  275.  
  276. /* returns number of powers of 5 found in this integer, alters integer */
  277. unsigned long eliminate_fives( unsigned long *i ){
  278.    unsigned long q;
  279.  
  280.    q = 0ul;
  281.    while( !( *i % 5ul ) ){
  282.       *i = *i/5ul;
  283.       q++;
  284.    }
  285.    return( q );
  286. }
  287.  
  288. /* returns number of powers of 2 found in this integer, alters integer */
  289. unsigned long eliminate_twos( unsigned long *i ){
  290.    unsigned long q;
  291.  
  292.    q = 0ul;
  293.    while( !( *i % 2ul ) ){
  294.       *i = *i/2ul;
  295.       q++;
  296.    }
  297.    return( q );
  298. }
  299.  
  300. //From: kcline@sun152.spd.dsccc.com ( Kevin Cline )
  301. #include <iostream.h>
  302. #include <stdlib.h>
  303.  
  304. // last digits of powers of two
  305. static int t0[] = {
  306.    6, 2, 4, 8 };
  307.  
  308. // log base two ( mod 5 ) of 0! - 4!
  309. static int t1[] = {
  310.    0, 0, 1, 0, 2 };
  311.  
  312. static int f( int i ) {
  313.    if ( i == 0 ) return 0;
  314.    return t1[i % 5] + i/5 + f( i/5 );
  315. }
  316.  
  317. static int lastNonZeroDigitOfFactorial( int i ) {
  318.    if ( i < 2 ) return 1;
  319.    return t0[f( i ) % 4];
  320. }
  321. //From: ian@rsd.bel.alcatel.be ( Ian Ward )
  322.  
  323. int last_digit2a ( int num )
  324. {
  325.    static int fred [] =
  326.    {
  327.       2, 6, 4, 2, 2, 4, 2, 8, 8, 8, 6, 8, 2, 6, 6, 2, 6, 4, 4, 4,
  328.       8, 4, 6, 8, 8, 6, 8, 2, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 6, 6
  329.    };
  330.    return num>1?fred[( num-2 )%40]:1;
  331. }
  332.  
  333. //From: kaskel@kirkuk.berkeley.edu ( Bruce Kaskel )
  334. int foo( int n )
  335. /* the input is n for n! */
  336. {
  337.    int i, j, u=1, t=0;
  338.    for( i=1;i<=n;i++ )
  339.    {
  340.       j=i;
  341.       while( !( j&1 ) ) {
  342.          j>>=1;
  343.          t++;
  344.       }
  345.       while( !( j%5 ) ) {
  346.          j/=5;
  347.          t--;
  348.       }
  349.       u=( u*( j%10 ) )%10;
  350.    }
  351.    if( t ) {
  352.       t&=3;
  353.       if( !t ) t=4;
  354.    } /* if t>0, only need t mod 4 */
  355.    for( i=0;i<t;i++ ) u=( u<<1 )%10; /* include factors of 2 */
  356.    return( u ); /* The rightmost non-zero digit of n! is u */
  357. }
  358.  
  359. //From: Chris Peikert <cpeikert@kamsc.seds.org>
  360. #include <iostream.h>
  361.  
  362. int rtDigit( int n ) {
  363.    int i;
  364.    long dig=1;
  365.    for( i=2; i<=n; i++ ) { // computing factorial
  366.  
  367.       dig *= i;
  368.       while( !( dig % 10 ) ) // chop of righthand 0s
  369.       dig /= 10;
  370.       dig %= 1000; // keep last three nonzero digits
  371.  
  372.    }
  373.    return ( dig % 10 ); // return last digit
  374.  
  375. }
  376.  
  377. //From: gusty@clark.net ( Harlan Messinger )
  378. // assume sufficient space was preallocated ( n+1 bytes )
  379. void getLastFactorialDigits( int results[], int n ) {
  380.  
  381.    results[0] = 1;
  382.    results[1] = 1;
  383.    for ( int i = 2; i <= n; ++i ) {
  384.       results[i] = results[i - 1] * i;
  385.       while ( results[i] % 10 == 0 )
  386.          results[i] /= 10;
  387.       results[i] = results[i] % 10;
  388.    }
  389.    return;
  390. }
  391. int ShowLastFactorialDigit( int results[], int n ) {
  392.    return results[n];
  393. }
  394.  
  395. //From: kaskel@kirkuk.berkeley.edu ( Bruce Kaskel )
  396. int a[20]={
  397.    1, 1, 1, 3, 3, 3, 3, 1, 1, 9, 9, 9, 9, 7, 7, 7, 7, 9, 9, 1
  398. };
  399. int b[4]={
  400.    6, 2, 4, 8
  401. };
  402.  
  403. int rightmost_nonzero_digit( int n )
  404. {
  405.    int u, t;
  406.    if( n<2 ) return( 1 );
  407.    foo2( n, &u, &t );
  408.    return( ( u*b[t] )%10 );
  409. }
  410.  
  411. int foo2( int n,int *x, int *y )
  412. {
  413.    int i=1, j=0, m=n>>1, u, f;
  414.    odds( n, &u, &f );
  415.    if ( m>1 ) foo2( m, &i, &j );
  416.    *x=( u*i )%10;
  417.    *y=( m+( 4-f )+j )&3;
  418.    return 0;
  419. }
  420.  
  421. int odds( int n, int *x, int *f )
  422. {
  423.    int q=1, r=0, s=n/5;
  424.    if( s>2 ) odds( s, &q, &r );
  425.    *x=( q*a[n%20] )%10;
  426.    *f=( r+( ( s+1 )>>1 ) )&3;
  427.    return 0;
  428. }
  429. #ifdef TEST
  430.  
  431. #ifndef FALSE
  432. #define FALSE 0
  433. #endif
  434.  
  435. #ifndef TRUE
  436. #define TRUE !FALSE
  437. #endif
  438.  
  439. int results[1001];
  440. #include <time.h>
  441. int main( int argc, char **argv )
  442. {
  443.  
  444.    int i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, ia, ib, ic;
  445.    char b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc;
  446.    char pszString[80];
  447.    int n;
  448.    int j;
  449.  
  450.    b0 = b1 = b2 = b3 = b4 = b5 = b6 = b7 = b8 = b9 = ba = bb = bc = TRUE;
  451.    getLastFactorialDigits( results, 1000 );
  452.    /* Agreement test: */
  453.    puts( "*** AGREEMENT TESTS ***" );
  454.    for ( n = 1; n <= 1000; n++ )
  455.    {
  456.       i0 = iLastDigit( n ); /* This was is ASSUMED to be infallable */
  457.       if ( b1 )
  458.          i1 = last_digit( n );
  459.       if ( b2 )
  460.          i2 = last_digit2( n );
  461.       if ( b3 )
  462.          i3 = last_digit2a( n );
  463.       if ( b4 )
  464.          i4 = last_non_zero_digit_of_factorial( n );
  465.       if ( b5 )
  466.          i5 = rightmost_nonzero_digit( n );
  467.       if ( b6 )
  468.          i6 = rtDigit( n );
  469.       if ( b7 )
  470.          i7 = factorial_lsd( n );
  471.       if ( b8 )
  472.          i8 = f( n );
  473.       if ( b9 )
  474.          i9 = lastNonZeroDigitOfFactorial( n );
  475.       if ( ba )
  476.          ia = foo( n );
  477.       if ( bb )
  478.          ib = ShowLastFactorialDigit( results, n );
  479.       if ( bc )
  480.          ic = fact_lsd( ( long ) n );
  481.  
  482.       if ( i0 != i1 && b1 )
  483.       {
  484.          b1 = FALSE;
  485.          printf( "Method 1 failed at %d.\n", n );
  486.       }
  487.  
  488.       if ( i0 != i2 && b2 )
  489.       {
  490.          b2 = FALSE;
  491.          printf( "Method 2 failed at %d.\n", n );
  492.       }
  493.  
  494.       if ( i0 != i3 && b3 )
  495.       {
  496.          b3 = FALSE;
  497.          printf( "Method 3 failed at %d.\n", n );
  498.       }
  499.  
  500.       if ( i0 != i4 && b4 )
  501.       {
  502.          b4 = FALSE;
  503.          printf( "Method 4 failed at %d.\n", n );
  504.       }
  505.  
  506.       if ( i0 != i5 && b5 )
  507.       {
  508.          b5 = FALSE;
  509.          printf( "Method 5 failed at %d.\n", n );
  510.       }
  511.  
  512.       if ( i0 != i6 && b6 )
  513.       {
  514.          b6 = FALSE;
  515.          printf( "Method 6 failed at %d.\n", n );
  516.       }
  517.  
  518.       if ( i0 != i7 && b7 )
  519.       {
  520.          b7 = FALSE;
  521.          printf( "Method 7 failed at %d.\n", n );
  522.       }
  523.  
  524.       if ( i0 != i8 && b8 )
  525.       {
  526.          b8 = FALSE;
  527.          printf( "Method 8 failed at %d.\n", n );
  528.       }
  529.  
  530.       if ( i0 != i9 && b9 )
  531.       {
  532.          b9 = FALSE;
  533.          printf( "Method 9 failed at %d.\n", n );
  534.       }
  535.  
  536.       if ( i0 != ia && ba )
  537.       {
  538.          ba = FALSE;
  539.          printf( "Method a failed at %d.\n", n );
  540.       }
  541.  
  542.       if ( i0 != ib && bb )
  543.       {
  544.          bb = FALSE;
  545.          printf( "Method b failed at %d.\n", n );
  546.       }
  547.       if ( i0 != ic && bc )
  548.       {
  549.          bc = FALSE;
  550.          printf( "Method c failed at %d.\n", n );
  551.       }
  552.  
  553.    }
  554.    if (!b1 )
  555.       puts( "last_digit( n ) failed." );
  556.    else
  557.       puts( "last_digit( n ) succeeded!" );
  558.    if (!b2 )
  559.       puts( "last_digit2( n ) failed." );
  560.    else
  561.       puts( "last_digit2( n ) succeeded!" );
  562.    if (!b3 )
  563.       puts( "last_digit2a( n ) failed." );
  564.    else
  565.       puts( "last_digit2a( n ) succeeded!" );
  566.    if (!b4 )
  567.       puts( "last_non_zero_digit_of_factorial( n ) failed." );
  568.    else
  569.       puts( "last_non_zero_digit_of_factorial( n ) succeeded." );
  570.    if (!b5 )
  571.       puts( "rightmost_nonzero_digit( n ) failed." );
  572.    else
  573.       puts( "rightmost_nonzero_digit( n ) succeeded!" );
  574.    if (!b6 )
  575.       puts( "rtDigit( n ) failed." );
  576.    else
  577.       puts( "rtDigit( n ) succeeded!" );
  578.    if (!b7 )
  579.       puts( "factorial_lsd( n ) failed." );
  580.    else
  581.       puts( "factorial_lsd( n ) succeeded!" );
  582.    if (!b8 )
  583.       puts( "f( n ) failed." );
  584.    else
  585.       puts( "f( n ) succeeded." );
  586.    if (!b9 )
  587.       puts( "lastNonZeroDigitOfFactorial( n ) failed." );
  588.    else
  589.       puts( "lastNonZeroDigitOfFactorial( n ) succeeded!" );
  590.    if (!ba )
  591.       puts( "foo( n ) failed." );
  592.    else
  593.       puts( "foo( n ) succeeded!" );
  594.    if (!bb )
  595.       puts( "ShowLastFactorialDigit( results, n ) failed." );
  596.    else
  597.       puts( "ShowLastFactorialDigit( results, n ) succeeded!" );
  598.    if (!bc )
  599.       puts( "fact_lsd( n ) failed." );
  600.    else
  601.       puts( "fact_lsd( n ) succeeded!" );
  602.  
  603.  
  604.    puts( "*** SPEED TESTS ***" );
  605.    printf("Start for direct lookup = %s\n", _strtime( pszString ) );
  606.    for ( j = 0; j < 100; j++ )
  607.       for ( n = 1; n <= 1000; n++ )
  608.       {
  609.          i0 = iLastDigit( n ); /* This was is ASSUMED to be infallable */
  610.       }
  611.    printf("Start for rightmost_nonzero_digit( n ) = %s\n", _strtime( pszString ) );
  612.    for ( j = 0; j < 100; j++ )
  613.       for ( n = 1; n <= 1000; n++ )
  614.       {
  615.          i5 = rightmost_nonzero_digit( n );
  616.       }
  617.    printf("Start for factorial_lsd( n ) = %s\n", _strtime( pszString ) );
  618.    for ( j = 0; j < 100; j++ )
  619.       for ( n = 1; n <= 1000; n++ )
  620.       {
  621.          i7 = factorial_lsd( n );
  622.       }
  623.    printf("Start for lastNonZeroDigitOfFactorial( n ) = %s\n", _strtime( pszString ) );
  624.    for ( j = 0; j < 100; j++ )
  625.       for ( n = 1; n <= 1000; n++ )
  626.       {
  627.          i9 = lastNonZeroDigitOfFactorial( n );
  628.       }
  629.    printf("Start for foo( n ) = %s\n", _strtime( pszString ) );
  630.    for ( j = 0; j < 100; j++ )
  631.       for ( n = 1; n <= 1000; n++ )
  632.       {
  633.          ia = foo( n );
  634.       }
  635.    printf("Start for fact_lsd( n ) = %s\n", _strtime( pszString ) );
  636.    for ( j = 0; j < 100; j++ )
  637.       for ( n = 1; n <= 1000; n++ )
  638.       {
  639.          ia = fact_lsd( n );
  640.       }
  641.    printf("End for fact_lsd( n ) = %s\n", _strtime( pszString ) );
  642.  
  643.    return 0;
  644. }
  645. /*
  646. *** AGREEMENT TESTS ***
  647. Method 8 failed at 1.
  648. Method 4 failed at 2.
  649. Method 1 failed at 15.
  650. Method 2 failed at 15.
  651. Method 3 failed at 15.
  652. Method b failed at 15.
  653. Method 6 failed at 375.
  654. last_digit( n ) failed.
  655. last_digit2( n ) failed.
  656. last_digit2a( n ) failed.
  657. last_non_zero_digit_of_factorial( n ) failed.
  658. rightmost_nonzero_digit( n ) succeeded!
  659. rtDigit( n ) failed.
  660. factorial_lsd( n ) succeeded!
  661. f( n ) failed.
  662. lastNonZeroDigitOfFactorial( n ) succeeded!
  663. foo( n ) succeeded!
  664. ShowLastFactorialDigit( results, n ) failed.
  665. fact_lsd( n ) succeeded!
  666. *** SPEED TESTS ***
  667. Start for direct lookup = 14:11:20
  668. Start for rightmost_nonzero_digit( n ) = 14:11:20
  669. Start for factorial_lsd( n ) = 14:11:28
  670. Start for lastNonZeroDigitOfFactorial( n ) = 14:14:10
  671. Start for foo( n ) = 14:14:11
  672. Start for fact_lsd( n ) = 14:17:42
  673. End for fact_lsd( n ) = 14:20:17
  674. */
  675. #endif
  676. --*-*-*- Next Section -*-*-*--
  677.  
  678.